package leetcode.D200.T126;

import java.util.*;

class Solution {
    /*//解法1：dfs，会超时
    private int min = Integer.MAX_VALUE;
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new LinkedList<>();
        Set<String> set = new HashSet<>(wordList);
        List<String> temp = new LinkedList<>();
        temp.add(beginWord);
        dfs(beginWord, endWord, set, temp, result);
        return result;
    }
    private void dfs(String curWord, String endWord, Set<String> set, List<String> temp, List<List<String>> result) {
        if(curWord.equals(endWord)) {
            if(temp.size() < min) {
                result.clear();
                result.add(new LinkedList<>(temp));
                min = temp.size();
            } else if (temp.size() == min) {
                result.add(new LinkedList<>(temp));
            }
            return;
        }
        if(temp.size() > min) {
            return;
        }
        for (String s : set) {
            if(temp.contains(s)) {
                continue;
            }
            if(oneChanged(curWord, s)) {
                temp.add(s);
                dfs(s, endWord, set, temp, result);
                temp.remove(temp.size()-1);
            }
        }
    }
    private boolean oneChanged(String curWord, String s) {
        if(curWord.length() != s.length()) {
            return false;
        }
        int count = 0;
        for(int i=0; i<curWord.length(); ++i) {
            if(curWord.charAt(i) != s.charAt(i)) {
                count++;
            }
            if(count > 1) {
                return false;
            }
        }
        return count == 1;
    }*/
    /*// 解法二：dfs，但是通过HashSet来保存wordList，加快oneChanged的判断
    private int min = Integer.MAX_VALUE;
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new LinkedList<>();
        List<String> temp = new LinkedList<>();
        Set<String> set = new HashSet<>(wordList);
        temp.add(beginWord);
        dfs(endWord, set, temp, result);

        return result;
    }
    private void dfs(String endWord, Set<String> set, List<String> temp, List<List<String>> result) {
        if(temp.size() > min) {
            return;
        }
        String curWord = temp.get(temp.size()-1);
        if(curWord.equals(endWord)) {
            if(temp.size() < min) {
                min = temp.size();
                result.clear();
                result.add(new LinkedList<>(temp));
            } else if (temp.size() == min) {
                result.add(new LinkedList<>(temp));
            }
            return;
        }
        List<String> similarWords = getSimilarWords(curWord, set);
        for (String word : similarWords) {
            if(temp.contains(word)) {
                continue;
            }
            temp.add(word);
            dfs(endWord, set, temp, result);
            temp.remove(temp.size()-1);
        }
    }
    private List<String> getSimilarWords(String curWord, Set<String> set) {
        List<String> result = new LinkedList<>();
        char[] chs = curWord.toCharArray();
        for(int i=0; i<curWord.length(); ++i) {
            char oldChar = chs[i];
            for(int j=0; j<26; ++j) {
                char temp = (char)('a'+j);
                if(temp == oldChar) {
                    continue;
                }
                chs[i] = temp;
                String target = String.valueOf(chs);
                if(set.contains(target)) {
                    result.add(target);
                }
            }
            chs[i] = oldChar;
        }
        return result;
    }*/
    /*// 解法三：bfs+dfs：先用bfs找到最短路径，再dfs求解
    private int min = 0;
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new LinkedList<>();
        Set<String> wordSet = new HashSet<>(wordList);
        if(!wordSet.contains(endWord)) {
            return result;
        }
        Map<String, List<String>> map = bfs(beginWord, endWord, wordSet);
        List<String> temp = new LinkedList<>();
        temp.add(beginWord);
        dfs(result, temp, endWord, map);
        return result;
    }
    private Map<String, List<String>> bfs(String beginWord, String endWord, Set<String> wordSet) {
        Map<String, List<String>> similarWords = new HashMap<>();
        Deque<String> dq = new LinkedList<>();
        dq.addLast(beginWord);
        while(!dq.isEmpty()) {
            int size = dq.size();
            min++;
            for(int i=0; i<size; ++i) {
                String front = dq.removeFirst();
                if(front.equals(endWord)) {
                    dq.clear();
                    break;
                }
                List<String> neighbors = null;
                if(!similarWords.containsKey(front)) {
                    neighbors = getNeighbors(front, wordSet);
                    similarWords.put(front, neighbors);
                }
                neighbors = similarWords.get(front);
                for (String neighbor : neighbors) {
                    dq.addLast(neighbor);
                }
            }
        }
        return similarWords;
    }
    private List<String> getNeighbors(String word, Set<String> wordSet) {
        List<String> neighbors = new LinkedList<>();
        char[] chs = word.toCharArray();
        for(int i=0; i<chs.length; ++i) {
            char oldChar = chs[i];
            for(int j=0; j<26; ++j) {
                char letter = (char)(j + 'a');
                if(letter == oldChar) {
                    continue;
                }
                chs[i] = letter;
                String temp = String.valueOf(chs);
                if(wordSet.contains(temp)) {
                    neighbors.add(temp);
                }
            }
            chs[i] = oldChar;
        }
        return neighbors;
    }
    private void dfs(List<List<String>> result, List<String> temp, String endWord, Map<String, List<String>> map) {
        String curWord = temp.get(temp.size()-1);
        if(temp.size() == min) {
            if(curWord.equals(endWord)) {
                result.add(new ArrayList<>(temp));
            }
            return;
        }
        List<String> neighbors = map.get(curWord);
        for (String neighbor : neighbors) {
            if(temp.contains(neighbor)) {
                continue;
            }
            temp.add(neighbor);
            dfs(result, temp, endWord, map);
            temp.remove(temp.size()-1);
        }
    }*/
    /*// 解法4：dfs+bfs，bfs找最短路径，dfs求解，在解法3的基础上加入了路径剪枝————————依旧超时
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        List<List<String>> result = new LinkedList<>();
        if(!wordSet.contains(endWord)) {
            return result;
        }
        Map<String, Integer> wordLevel = new HashMap<>();
        Map<String, List<String>> map = new HashMap<>();
        if(!bfs(beginWord, endWord, wordSet, wordLevel, map)) {
            return result;
        }
        List<String> temp = new LinkedList<>();
        temp.add(beginWord);
        dfs(endWord, result, temp, map, wordLevel);
        return result;
    }
    private void dfs(String endWord, List<List<String>> result, List<String> temp, Map<String, List<String>> map, Map<String, Integer> wordLevel) {
        String curWord = temp.get(temp.size()-1);
        if(temp.size() == wordLevel.get(endWord)) {
            if(curWord.equals(endWord)) {
                result.add(new ArrayList<>(temp));
            }
            return;
        }
        List<String> neighbors = map.get(curWord);
        for (String neighbor : neighbors) {
            if(wordLevel.containsKey(neighbor) && wordLevel.get(neighbor) > temp.size()) {
                temp.add(neighbor);
                dfs(endWord, result, temp, map, wordLevel);
                temp.remove(temp.size()-1);
            }
        }
    }
    private boolean bfs(String beginWord, String endWord, Set<String> wordSet, Map<String, Integer> wordLevel, Map<String, List<String>> map) {
        Deque<String> dq = new LinkedList<>();
        dq.addLast(beginWord);
        int level = 0;
        while(!dq.isEmpty()) {
            int size = dq.size();
            level++;
            for(int i=0; i<size; ++i) {
                String front = dq.removeFirst();
                if(front.equals(endWord)) {
                    wordLevel.put(front, level);
                    return true;
                }
                List<String> neighbors = null;
                if(map.containsKey(front)) {
                    neighbors = map.get(front);
                } else {
                    neighbors = getNeighbors(front, wordSet);
                    map.put(front, neighbors);
                    wordLevel.put(front, level);
                }
                for (String neighbor : neighbors) {
                    if(!wordLevel.containsKey(neighbor)) {
                        dq.addLast(neighbor);
                    }
                }
            }
        }
        return false;
    }
    private List<String> getNeighbors(String word, Set<String> wordSet) {
        List<String> neighbors = new LinkedList<>();
        char[] chs = word.toCharArray();
        for(int i=0; i<chs.length; ++i) {
            char oldChar = chs[i];
            for(int j=0; j<26; ++j) {
                char letter = (char)(j + 'a');
                if(letter == oldChar) {
                    continue;
                }
                chs[i] = letter;
                String temp = String.valueOf(chs);
                if(wordSet.contains(temp)) {
                    neighbors.add(temp);
                }
            }
            chs[i] = oldChar;
        }
        return neighbors;
    }*/
    // 解法5：纯bfs，不借助dfs得到解，而是在bfs的同时得到解，但是bfs的队列节点要改为List
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new LinkedList<>();
        Set<String> wordSet = new HashSet<>(wordList);
        if(!wordSet.contains(endWord)) {
            return result;
        }
        bfs(beginWord, endWord, wordSet, result);
        return result;
    }
    private void bfs(String beginWord, String endWord, Set<String> wordSet, List<List<String>> result) {
        Deque<List<String>> dq = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        List<String> path = new LinkedList<>();
        path.add(beginWord);
        dq.addLast(path);
        boolean isFind = false;
        while(!dq.isEmpty()) {
            int size = dq.size();
            Set<String> lastVisited = new HashSet<>(visited);
            for (int i = 0; i < size; i++) {
                path = dq.removeFirst();
                String curWord = path.get(path.size()-1);
                if(curWord.equals(endWord)) {
                    isFind = true;
                    result.add(new ArrayList<>(path));
                    continue;
                }
                List<String> neighbors = getNeighbors(curWord, wordSet);
                for (String neighbor : neighbors) {
                    if(!neighbor.equals(endWord) && lastVisited.contains(neighbor)) {
                        continue;
                    }
                    path.add(neighbor);
                    visited.add(curWord);
                    dq.addLast(new LinkedList<>(path));
                    path.remove(path.size()-1);
                }
            }
            if(isFind) {
                break;
            }
        }
    }
    private List<String> getNeighbors(String word, Set<String> wordSet) {
        List<String> neighbors = new LinkedList<>();
        char[] chs = word.toCharArray();
        for(int i=0; i<chs.length; ++i) {
            char oldChar = chs[i];
            for(int j=0; j<26; ++j) {
                char letter = (char)(j + 'a');
                if(letter == oldChar) {
                    continue;
                }
                chs[i] = letter;
                String temp = String.valueOf(chs);
                if(wordSet.contains(temp)) {
                    neighbors.add(temp);
                }
            }
            chs[i] = oldChar;
        }
        return neighbors;
    }
}